package 剑指offer;

import java.util.concurrent.TimeUnit;

public class Offer14_JZ67 {

    public static int cutRope(int target) {
        if (target < 2) return 0;
        if (target == 2) return 1;
        if (target == 3) return 3;
        int[] products = new int[target+1];
        products[0] = 0;
        products[1] = 1;
        products[2] = 1;
        products[3] = 3;
        for (int i=4; i<=target; i++) {
            int max = 0;
            for (int j=1; j<=i/2; j++) {
                int product = products[j] * products[i-j];
                max = Math.max(product, max);
            }
            products[i] = max;
        }
        return products[target];
    }

    public static int cutRope2(int target) {
        if (target < 2) return 0;
        if (target == 2) return 1;
        if (target == 3) return 2;
        int cope3 = target/3;
        if (target - cope3*3 == 1) {
            cope3 -= 1;
        }
        int cope2 = (target-cope3*3) / 2;
        return (int) (Math.pow(3, cope3) * (int) Math.pow(2, cope2));
    }

    public static void main(String[] args) {
        long starttime =  System.nanoTime();
        System.out.println(cutRope(2));
        System.out.println(cutRope2(8));
        System.out.println(System.nanoTime() - starttime);
    }
}
